#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 5005;
int num;
int fa[MAXN];
// 修改后的查找函数
int findfa(int x){
    // 如果是根节点（fa[x]==0）或到达了根节点
    if(fa[x] == 0) return x;
    // 路径压缩：将沿途的每个节点都直接指向根节点
    fa[x] = findfa(fa[x]);
    return fa[x];
}
void unite(int a, int b) {
    a = findfa(a);
    b = findfa(b);
    if (a != b) {
        fa[a] = b;
        num--;
    }
}
// 合并函数保持不变
void makeset(int a,int b){
    num--;
    fa[a]=b;
}
int main(){
    int n,m,q;
    cin>>n>>m>>q;
    // 初始化
    memset(fa, 0, sizeof(fa));
    num=n;
    
    // 处理边的关系
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if(!fa[a]&&!fa[b]){
            makeset(a,b);
            continue;
        }
        if(fa[a]&&!fa[b]){
            int fa1=findfa(a);
           if(fa1!=b)fa[fa1]=b;
        }
        if(fa[b]&&!fa[a]){
            fa[a]=findfa(b);
            num--;
            continue;
        }
        if(fa[b]&&fa[a]){
            int fa1=findfa(a);
            int fa2=findfa(b);
            if(fa1!=fa2){
                fa[fa1]=fa2;
                num--;
            }
            continue;
        }
    }
    
    // 处理查询
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        // 先检查输入的合法性
        if(a < 1 || a > n || b < 1 || b > n){
            cout<<"Invalid input"<<endl;
            continue;
        }
        int root_a = findfa(a);
        int root_b = findfa(b);
        if(root_a == root_b)
            cout<<"In the same gang."<<endl;
        else 
            cout<<"In different gangs."<<endl;
    }
    cout<<num;
    return 0;
}
//使用统一合并函数，若两者不一样，则合并。